
def BoxPosition(board):
    return board >> 60

_mapPosition = {}
def _Positions(hash):
    if hash in _mapPosition:
        return _mapPosition[hash]
    positions = [i for i in range(20) if hash & (1<<i)]
    _mapPosition[hash] = positions
    return positions

def VPositions(board):
    return _Positions((board >> 40) & 0xfffff)

def HPositions(board):
    return _Positions((board >> 20) & 0xfffff)

def DPositions(board):
    return _Positions(board & 0xfffff)

def BMask(position):
    return 51 << position

def VMask(position):
    return 17 << position

def HMask(position):
    return 3 << position

def DMask(position):
    return 1 << position

def BHash(position):
    return position << 60

def VHash(position):
    return 1 << (40+position)

def HHash(position):
    return 1 << (20+position)

def DHash(position):
    return 1 << position

def BoardMask(board):
    mask = BMask(BoxPosition(board))
    for position in VPositions(board):
        assert(mask & VMask(position) == 0)
        mask ^= VMask(position)
    for position in HPositions(board):
        assert(mask & HMask(position) == 0)
        mask ^= HMask(position)
    for position in DPositions(board):
        assert(mask & DMask(position) == 0)
        mask ^= DMask(position)
    return mask

_mapSquarePositions = [{} for i in range(20)]
def _NextPosition(position, square_mask):
    _map = _mapSquarePositions[position]
    if square_mask in _map:
        return _map[square_mask]
    _ = []
    if square_mask & 0x11111 == 0: _.append(position-1)
    if square_mask & 0x88888 == 0:_.append(position+1)
    if square_mask & 0xf == 0: _.append(position-4)
    if square_mask & 0xf0000 == 0: _.append(position+4)
    _map[square_mask] = _
    return _
    
def NextPositions(position, board_mask, square_mask_func, _continue, _map):
    if board_mask in _map:
        return _map[board_mask]
    _ = set()
    for next in _NextPosition(position, square_mask_func(position)):
        if square_mask_func(next) & board_mask == 0:
            _.add(next)
            if _continue:
                _ |= NextPositions(next, board_mask, square_mask_func, False, _map)
    if _continue:
        _map[board_mask] = _
    return _

_mapBox = [{} for i in range(20)]
_mapV = [{} for i in range(20)]
_mapH = [{} for i in range(20)]
_mapD = [{} for i in range(20)]
def NextBoards(board):
    b_position = BoxPosition(board)
    v_positions = VPositions(board)
    h_positions = HPositions(board)
    d_positions = DPositions(board)
    mask = BMask(b_position)
    for position in v_positions:
        assert(mask & VMask(position) == 0)
        mask ^= VMask(position)
    for position in h_positions:
        assert(mask & HMask(position) == 0)
        mask ^= HMask(position)
    for position in d_positions:
        assert(mask & DMask(position) == 0)
        mask ^= DMask(position)
    for position in NextPositions(b_position, mask^BMask(b_position), BMask, True, _mapBox[position]): 
        yield board ^ BHash(b_position) ^ BHash(position)
    for v_position in v_positions:
        for position in NextPositions(v_position, mask^VMask(v_position), VMask, True, _mapV[v_position]):
            if v_position != position:
                yield board ^ VHash(v_position) ^ VHash(position)
    for h_position in h_positions:
        for position in NextPositions(h_position, mask^HMask(h_position), HMask, True, _mapH[h_position]):
            if h_position != position:
                yield board ^ HHash(h_position) ^ HHash(position)
    for d_position in d_positions:
        for position in NextPositions(d_position, mask^DMask(d_position), DMask, True, _mapD[d_position]):
            if d_position != position:
                yield board ^ DHash(d_position) ^ DHash(position)

def Solve(board):
    if BoxPosition(board) == 13:
        return
    _mapBoard = {board:board}
    boards = [[board]]
    while True:
        lasts, nexts = boards[-1], []
        boards.append(nexts)
        for current in lasts:
            for next in NextBoards(current):
                if next not in _mapBoard:
                    _mapBoard[next] = current
                    nexts.append(next)
                    if BoxPosition(next) == 13:
                        yield next
                        while next != board:
                            next = _mapBoard[next]
                            yield next
                        return

import time
start = time.time()
seq = list(reversed([i for i in Solve(1153079980847042569)]))
print 'use time:', time.time() - start
print 'lenght:', len(seq)
for i in seq:
    print i
